#pragma once

#include <vector>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <unordered_map>

// 参照树的表达方式，但图一般不这么表示
struct Vertex {
    int value;
    std::vector<Vertex*> neighbors;
};

typedef std::vector<std::vector<int>>              AdjMatrix;
typedef std::unordered_map<int, std::vector<int> > AdjList;

class GraphAdjMat {
public:
    /**
     * @brief 构建含有_numVertex个节点的空图，即不包含任何边
     * 
     * @param _numVertex  图中节点的数量
     */
    GraphAdjMat(const int _numVertex) {
        this->_numVertex = _numVertex;
        for (int i = 0; i < this->_numVertex; i++) {
            this->_adjMatrix.push_back(std::vector<int>(_numVertex, 0));
        }
    }

    /**
     * @brief 构建含有_numVertex个节点的空图, 使用参数中的边填充
     * 
     * @param _numVertex   图中节点的数量
     * @param edges        图中的边, 是一个点对的列表
     */
    GraphAdjMat(const int _numVertex, const AdjMatrix& edges) {
        this->_numVertex = _numVertex;
        for (int i = 0; i < this->_numVertex; i++) {
            this->_adjMatrix.emplace_back(std::vector<int>(_numVertex, 0));
        }

        for (const std::vector<int>& edge : edges) {
            this->_adjMatrix[edge[0]][edge[1]] = 1;
            this->_adjMatrix[edge[1]][edge[0]] = 1;
        }
    }

    int size() {
        return this->_numVertex;
    }

    void addVertex() {
        auto n = this->_numVertex;
        this->_numVertex++;
        // 给邻接矩阵添加一行
        this->_adjMatrix.emplace_back(std::vector<int>(n, 0));
        // 给邻接矩阵添加一列
        for (std::vector<int>& vec : this->_adjMatrix) {
            vec.push_back(0);
        }
    }

    void addEdge(int i, int j) {
        if (outRange(i) || outRange(j)) {
            throw std::out_of_range(std::string("顶点不存在!"));
            return;
        }
        this->_adjMatrix[i][j] = 1;
        this->_adjMatrix[j][i] = 1;
    }

    void removeEdge(int i, int j) {
        if (outRange(i) || outRange(j)) {
            throw std::out_of_range(std::string("顶点不存在!"));
            return;
        }

        this->_adjMatrix[i][j] = 0;
        this->_adjMatrix[j][i] = 0;
    }

    void printGraph() {
        std::cout << "顶点总数: " <<  this->_numVertex << std::endl;
        std::cout << "=============================" << std::endl;
        std::cout << std::endl << std::endl;

        std::cout << "邻接矩阵: " << std::endl;
        std::cout << "=============================" << std::endl;
        for (const std::vector<int>& row : this->_adjMatrix) {
            for (const int& val : row) {
                std::cout << val << " ";
            }
            std::cout << std::endl;
        }
        std::cout << std::endl;
    }

    AdjMatrix& getAdjMatrix() {
        return this->_adjMatrix;
    }

private:
    inline bool outRange(int idx) {
        if (idx < 0 || idx >= this->_numVertex) {
            return true;
        }
        return false;
    }

private:
    int _numVertex;                           // 顶点数量
    std::vector<std::vector<int>>  _adjMatrix;  // 邻接矩阵
};


class GraphAdjList {
public:
    GraphAdjList(const int numVertex) : _numVertex(numVertex) {
        for (int i = 0; i < numVertex; i++) {
            this->_adjList[i] = std::vector<int>(0, 0);
        }
    }

    GraphAdjList(const int numVertex, const AdjMatrix& edges) {
        this->_numVertex = numVertex;
        for (int i = 0; i < numVertex; i++) {
            this->_adjList[i] = std::vector<int>(0, 0);
        }

        for (const std::vector<int>& edge : edges) {
            int from_ = edge[0];
            int to_   = edge[1];
            if (outRange(from_) || outRange(to_)) {
                throw std::out_of_range(std::string("顶点不存在!"));
                return;
            }

            this->_adjList[from_].push_back(to_);
            this->_adjList[to_].push_back(from_);
        }
    }

    GraphAdjList(const int numVertex, const AdjList& adjList) {
        this->_numVertex = numVertex;
        for (int i = 0; i < numVertex; i++) {
            this->_adjList[i] = std::vector<int>(0, 0);
            for (const int& val : adjList.at(i)) {
                this->_adjList[i].push_back(val);
            }
        }
    }

    int size() const {
        return this->_numVertex;
    }

    void printGraph() const {
        std::cout << "顶点总数: " <<  this->_numVertex << std::endl;
        std::cout << "=============================" << std::endl;
        std::cout << std::endl << std::endl;

        std::cout << "邻接表: " << std::endl;
        std::cout << "=============================" << std::endl;
        for (int i = 0; i < _numVertex; i++) {
            printf("%2d : ", i);
            const std::vector<int>& list = this->_adjList.at(i);
            for (const int val : list) {
                printf("%2d ", val);
            }
            printf("\n");
        }
        printf("\n");
    }

    AdjList& getAdjList()  {
        return this->_adjList;
    }

private:
    inline bool outRange(int idx) const {
        if (idx < 0 || idx >= this->_numVertex) {
            return true;
        }
        return false;
    }

private:
    int     _numVertex;      // 顶点数量
    AdjList _adjList;        // 邻接表
};